Successful approaches to program induction require a hand-engineered domain-specific language (DSL), constraining the space of allowed programs and imparting prior knowledge of the domain. We contribute a program induction algorithm that learns a DSL while jointly training a neural network to efficiently search for programs in the learned DSL. We use our model to synthesize functions on lists, edit text, and solve symbolic regression problems, showing how the model learns a domain-specific library of program components for expressing solutions to problems in the domain.

Summary A method for learning a DSL for program synthesis together with a search algorithm in that DSL is presented. The method proceeds iteratively, trying to solve tasks with the current DSL, and then extracting new DSL components from the solutions. Experiments show that bootstrapping the method with a DSL made up of trivial primitives is sufficient to discover common high-level constructs present in manually constructed DSLs. The paper tackles an important problem (DSL design) in an elegant and novel way. The clarity of the paper is not perfect, as the details of the idea require more space than the 8 pages available, but it clearly is stepping stone towards a new generation of program synthesis approaches.

Successful approaches to program induction require a hand-engineered domain-specific language (DSL), constraining the space of allowed programs and imparting prior knowledge of the domain. We contribute a program induction algorithm that learns a DSL while jointly training a neural network to efficiently search for programs in the learned DSL. We use our model to synthesize functions on lists, edit text, and solve symbolic regression problems, showing how the model learns a domain-specific library of program components for expressing solutions to problems in the domain. Papers published at the Neural Information Processing Systems Conference.